/******************************************************************************************
 * Data Structures in C++
 * ISBN: 7-302-33064-6 & 7-302-33065-3 & 7-302-29652-2 & 7-302-26883-3
 * Junhui DENG, deng@tsinghua.edu.cn
 * Computer Science & Technology, Tsinghua University
 * Copyright (c) 2006-2013. All rights reserved.
 ******************************************************************************************/

#pragma once

#include <queue>

template <typename Tv, typename Te> 
void Graph<Tv, Te>::bfs(int s) { 
   reset(); int clock = 0; int v = s; 
   do 
      if (UNDISCOVERED == status(v)) 
         BFS(v, clock); 
   while (s != (v = (++v % n))); 
}

template <typename Tv, typename Te> 
void Graph<Tv, Te>::BFS(int v, int& clock) { 
   queue<int> Q; 
   status(v) = DISCOVERED; Q.push(v); 
   while (!Q.empty()) {
      int v = Q.front(); dTime(v) = ++clock;
	  Q.pop();
      for (int u = firstNbr(v); -1 < u; u = nextNbr(v, u)) 
         if (UNDISCOVERED == status(u)) { 
            status(u) = DISCOVERED; Q.push(u); 
            status(v, u) = TREE; parent(u) = v; 
         } else { 
            status(v, u) = CROSS; 
         }
         status(v) = VISITED; 
   }
}
